package algorithm.hashtable;

import java.util.HashMap;
import java.util.Map;

/**
 * 219. Contains Duplicate II
 * LeetCode: https://leetcode.com/problems/contains-duplicate-ii/
 * Difficulty: Easy
 * Related Topics: Array, HashTable
 *
 * 给一个数组 nums 和一个数字 k。
 * 找出数组中是否有两个数字一样，并且数字的 index 差的绝对值不大于k
 *
 *
 * Created by yzy on 2019-05-05 19:28
 */
public class ContainsDuplicateII {


    /**
     * 思路：
     * 利用HashMap的特性. key=nums的值, val=nums的索引
     * 当put的时候，如果原来key有值，则会返回旧的val，并且把新的val替换进去。
     * 如果能拿到旧val，那说明存在重复的，比较当前index 和 旧 val 即可
     *
     * Runtime: 7ms (beats 92.20%)
     * Memory:  43.5MB (beats 39.60%)
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            Integer oldVal = map.put(nums[i], i);
            if(oldVal != null && i-oldVal<=k){
                return true;
            }
        }
        return false;
    }

}
